背景觀念

• 多個行程可以同時執行：

1. 行程可以在任何時候被中斷，因為有時候執行到一半，控制CPU的權力會轉交給OS，所以會造成中斷的情形出現。

• 有些行程可能會共享data或共同執行程式，所以某些data與程式就需要被保護，不然可能會造成前後data的矛盾。
• 為了維持data的一致，所以要求機制確認cooperating precesses是有順序的執行。
• 有時候會造成consumer-producer problem：因為producer與consumer會有共同整數的counter，會持續檢查buffer內的位置空間，所以會產生synchronization problem。

Producer程式說明
while (true) {
/*produce an item in next produced */

       while (counter == BUFFER_SIZE)；   /* =>表示buffer是額滿狀態*/
                   /*do nothing */     /* =>額滿就不做任何事*/
       buffer[in] = next_produced；       /* =>如果沒額滿的話，會產生一個資料，放進buffer array-[in]內，放進去後下一個的位置就是下一行程式所表示的位置*/
       in = (in+1) % BUFFER_SIZE；     /* =>將資料移到下個位置*/
       counter ++；        /* =>counter就會增加*/

Consumer程式說明
while (true) {
while (counter == 0 )； /* => 如果buffer=0，就沒有東西可以消耗*/
/do nothing/ /* =>程式等待 /
next_consumed = buffer[out]； / =>如果buffer不等於0的話，便從[out]中讀取一個資料出來*/
out = (out + 1) % BUFFER_SIZE；
counter --； /因為讀取了一個資料，所以要減1/
/*consume the item in next consumed */

Race Condition

• 可以像以下方式一樣執行counter ++：

1. register1 = counter
2. register1 = register1 + 1
3. counter = register1

• 可以像以下方式一樣執行counter --：

1. register2 = counter
2. register2 = register2 - 1
3. counter = register2

• 可以以一個例子說明「Race Condition」是甚麼意思：
  S0：producer execute register1 = counter {register1 = 5}
  S1：producer execute register1 = register1 + 1 {register1 = 6}
  interrupt
  S2：consumer execute register2 = counter {register2 = 5}
  S3：consumer execute register2 = register2 - 1 {register2 = 4}
  interrupt
  S4：producer execute counter = register1 {counter = 6}
  interupt
  S5：consumer execute counter = register2 {counter = 4}
  錯誤結果
  =>因為producer和consumer需要同時執行，而且在執行counter ++與counter --的時候，容易發生interrupt的情形，會造成錯誤的結果，而這種時候就稱作為「Race Condiition」。
• 在兩個process在共享data的時候，很容易發生Race Condition。

Critical Section Problem

• 考慮在一個系統中，有n個processes {p0、p1、、、、p(n-1)}
• 每個process中有一段程式碼的區段，稱為「critical section」:

1. Process可能會改變共同的variables、updating table、writing file等。
2. 當一個process在critical section內時，其他processes便不可以在自己的critical section裡。

• 設計protocol或方法去解critical Section problem。
• 每個行程在進入critical section前，須先到「entry section」，離開時是「exit section」，再接著去執行「remainder section」。
• 程式說明：
  先產生一個process Pi：
  do {
  [entry section] /=>這邊是一段非常重要的程式碼/
  critical section /=>在這之中，OS需要想如何提供程式碼，或是工程師設計應用程式去使用，是非常重要的/
  [exit section] /結束離開/
  remainder section /接著是執行remainder section/
  } while (true)；
• Pi的Algorithm：
  在進入critical setion後：
  do {
  while ( turn == j )；
  critical section
  turn == j ；
  remainder section
  } while (true)；
  ===>在while (turn == j)這邊，會決定是哪個process進入critical section；如果條件不符，則不進入critical section，若是條件符合的話，便進入且做完工作，再將[turn = j ]這邊的條件做更改，再去執行remainder section。就目前來說是最簡單的方法。

Solution to Critical-Section Problem

• Mutual Exclusion：如果Pi再critical section中的話，則其他process就不能在它們自己的critical section中執行。
• Progress：如果在critical section中，沒有process在執行，並存在著想進入critical section的process的話，就需要選擇process進入critical section，不能無限延期的停留在此階段。
• Bounding Waiting：在等待進入critical section的時間，必須是有期限的，不能是無窮盡的等待，要在Progress階段，每個process進入critical section後不能佔住不離開，所以要：

1. 每個processes必須要執行，且執行速度不能是0，但是實際執行速度不在意，重要有執行就好。

Critical-Section Handling in OS

• 有兩種方法是取決於kernel是preemptive或non-preemptive：

1. Preemptive：允許在kernel mode中，何時開始執行process。
2. Non-preemptive：執行到存在kernel mode、blocks或自願產生CPU。

Peterson's Solution

• 假設有兩個process，Pi和Pj。且這兩個可以獨立完成，不會被中斷。
• 共享兩個variables：

1. int turn； =>表示是輪到哪個process進入critical section。
2. Boolean flag[2] =>表示哪個process已經準備好進入critical section。

• Pi的Algorithm說明：
  do {
  flag [ i ] = ture ；
  turn = j ；
  while ( flag [ j ] && turn == j ) ；
  critical section flag [ i ] = false；
  remainder section
  } while (true) ；
  ===>{flag [ i ] =true}這段表示Pi已經準備好要進入critical section，但目前是Pj在使用。
  ===>{turn = j}表示目前是Pj在使用，所以Pi要等待，除非是變成turn = i，則Pi就可以進入執行，完成後將{flag [ i ] = false}表示出來，代表換成Pj，去做remainder section的事情。
• 可以證明滿足三個critical section的要求；

1. Mutual exclusin：如果Pi要進入critial section的話，要滿足flag [ j ] =false 或 turn =i的條件。
2. Progress要求滿足三種情況：
   1-Pj根本沒有要進入critical section，或Pi直接進入。
   2-Pj想進入，可是Pi搶先進入，所以換Pi進入，除非條件更改成符合Pj，才能事Pj進入。
   3-Pj已經完成，但想再進入的話，就必須要讓Pi進入執行完成，才能再次進入，形成一種輪流的狀態。
3. Bounded-waiting：Pi和Pj輪流進入critical section中執行。